package com.ldw.algorithm;

/**
 * 递归方法简单但效率低。
 * 动态规划方法效率较高，避免了重复计算。
 * 空间优化方法将空间复杂度减少到 O(1)。
 * 矩阵快速幂方法适用于大规模计算斐波那契数，时间复杂度 O(log n)。
 * 尾递归方法更适合语言支持尾调用优化的情况，但 Java 不提供直接支持。
 */
public class Fibonacci {
//    递归方法是最直观的，但效率较低，因为会有重复计算。
    public static   int fibanacci(int a){
        if (1==a||2==a){
            return 1;
        }
        else {
            return fibanacci(a-1)+fibanacci(a-2);
        }
    }

  /*  动态规划使用一个数组保存已计算的结果，从而避免重复计算，提高效率。*/
    public static int dynamicPlain(int a ){
        if (a<=1) {
            return 1;
        }
        int i[]=new int [a+1];
        i[0]=0;
        i[1]=1;
        for (int k=2; k<=a;k++){
             i[k]=i[k-1]+i[k-2];
        }
        return i[a];
    }

    /* 优化空间复杂度，只保存前两个数。 但是每次都要从头算起，时间复杂的会升高*/
    public static int savePre2(int index ){
        if (index<=1){
            return index;
        }

        int pre1=0;
        int pre2=1;
        for (int i=2;i<index;i++){
            int current=pre1+pre2;
            pre1=pre2;
            pre2=current;
        }
        return pre2;

    }

    public static void main(String[] args) {
        System.out.println(savePre2(7));
    }

}
